package bm55;

import java.util.ArrayList;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/9/13 0:01
 * BM55 没有重复项数字的全排列
 * https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1?tpId=295&tqId=701&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    ArrayList<ArrayList<Integer>> res; // 存储结果
    ArrayList<Integer> curRes; // 中间结果
    boolean[] check; // 标记数组


    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        res = new ArrayList<>();
        curRes = new ArrayList<>(); // 中间结果
        check = new boolean[num.length]; // 标记数组
        // 深搜回溯
        dfs(num);
        return res;
    }

    private void dfs(int[] num) {
        // 记录结果
        if (curRes.size() == num.length) {
            res.add(new ArrayList<>(curRes));
            return;
        }
        // 深搜
        for (int i = 0; i < num.length; i++) {
            if (!check[i]) {
                curRes.add(num[i]);
                check[i] = true;
                dfs(num);
                check[i] = false;
                curRes.remove(curRes.size() - 1);
            }
        }
    }
}
